import java.util.*;

/**
 * @author DCSGO
 * @version 1.0
 */
/*
题目2
小团在地图上放了3个定位装置，想依赖他们进行定位!
地图是一个n*n的棋盘，
有3个定位装置(x1,y1),(x2,y2),(x3,y3)，每个值均在[1, n]内。
小团在(a, b)位置放了一个信标，
每个定位装置会告诉小团它到信标的曼哈顿距离，也就是对于每个点，小团知道|xi-a|+|yi-b|
求信标位置，信标不唯一，输出字典序最小的。
输入n,然后是3个定位装置坐标，
最后是3个定位装置到信标的曼哈顿距离。
输出最小字典序的信标位置。
1 <= 所有数据值 <= 50000
 */
public class P5 {
    public static void main(String[] args) {
        /*int n = 7;
        int[] p1 = {7, 1};
        int[] p2 = {5, 7};
        int[] p3 = {3, 2};
        int d1 = 8;
        int d2 = 4;
        int d3 = 3;

        int[] ans = find(n, p1, p2, p3, d1, d2, d3);
        System.out.println(Arrays.toString(ans));//[3, 5]*/

        /*int n = 7;
        int[] p1 = {3, 3};
        int[] p2 = {6, 6};
        int[] p3 = {2, 7};
        int d1 = 3;
        int d2 = 3;
        int d3 = 2;

        int[] ans = find(n, p1, p2, p3, d1, d2, d3);
        System.out.println(Arrays.toString(ans));//[3, 6]*/

        int n = 7;
        int[] p1 = {2, 3};
        int[] p2 = {3, 4};
        int[] p3 = {4, 5};
        int d1 = 2;
        int d2 = 2;
        int d3 = 2;

        int[] ans = find(n, p1, p2, p3, d1, d2, d3);
        System.out.println(Arrays.toString(ans));//[2, 5]

    }

    public static int[] find(int n, int[] p1, int[] p2, int[] p3, int d1, int d2, int d3) {
        //找到最短距离 d1
        if (d1 > d2) {
            int tmp = d1;
            d1 = d2;
            d2 = tmp;
            int[] tmp1 = p1;
            p1 = p2;
            p2 = tmp1;
        }
        if (d1 > d3) {
            int tmp = d1;
            d1 = d3;
            d3 = tmp;
            int[] tmp1 = p1;
            p1 = p3;
            p3 = tmp1;
        }

        //广度优先遍历 找到圆周上的点
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        int[] curP = {p1[0] - d1, p1[1]};
        queue.add(curP);
        visited.add(curP[0] + "_" + curP[1]);

        //信标所在位置
        ArrayList<int[]> ans = new ArrayList<>();

        while (!queue.isEmpty()) {
            curP = queue.poll();
            //将符合条件的信标添加到ans
            if (curP[0] > 0 && curP[0] <= n
                    && curP[1] > 0 && curP[1] <= n
                    && distance(curP[0], curP[1], p2) == d2
                    && distance(curP[0], curP[1], p3) == d3) {
                ans.add(curP);
            }

            //找到超过1个信标就退出
            if (ans.size() > 1) {
                break;
            }

            //添加 p1 圆周上的点到 queue
            //左上
            add(curP[0] - 1, curP[1] - 1, d1, p1, queue, visited);
            //左下
            add(curP[0] - 1, curP[1] + 1, d1, p1, queue, visited);
            //右上
            add(curP[0] + 1, curP[1] - 1, d1, p1, queue, visited);
            //右下
            add(curP[0] + 1, curP[1] + 1, d1, p1, queue, visited);
        }

        if (ans.size() > 1) {
            //ans 中字典序最小的信标
            if (ans.get(0)[0] < ans.get(1)[0]) {
                return ans.get(0);
            } else if (ans.get(0)[0] == ans.get(0)[0]) {
                return ans.get(0)[1] < ans.get(1)[1] ? ans.get(0) : ans.get(1);
            } else {
                return ans.get(1);
            }
        } else {//仅找到一个信标
            return ans.get(0);
        }
    }

    //将在圆周上的点添加到队列 圆心p 半径 r
    public static void add(int x, int y, int r, int[] p, Queue<int[]> queue, Set<String> visited) {
        String key = x + "_" + y;
        if (distance(x, y, p) == r && !visited.contains(key)) {
            visited.add(key);
            queue.add(new int[]{x, y});
        }
    }

    //计算两点间的曼哈顿距离
    public static int distance(int x, int y, int[] p) {
        return Math.abs(x - p[0]) + Math.abs(y - p[1]);
    }
}
